package leetcode_100;

import java.util.ArrayList;
import java.util.List;



/**
 *@author 周杨
 *InsertInterval_57 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
 *describe: 每次加入的时候判断是否能够合并 如果能 找到其之后无法合并的坐标 并记录要删除的区间
 *			如果不能合并 且没有发生过合并 那么查找插入位置
 *2018年5月9日 下午9:07:00
 */
public class InsertInterval_57 {
	List<Interval> res; 
	static class Interval {
		      int start;
		      int end;
		      Interval() { start = 0; end = 0; }
		      Interval(int s, int e) { start = s; end = e; }
		  }
	public static void main(String[] args) {
		InsertInterval_57 test=new InsertInterval_57();
		Interval a=new Interval(1, 5);
		Interval b=new Interval(3, 5);
		Interval c=new Interval(6,7);
		Interval d=new Interval(8,10);
		
		Interval e=new Interval(12,16);
		/*Interval a=new Interval(2, 3);
		Interval b=new Interval(5, 5);
		Interval c=new Interval(2,2);
		Interval d=new Interval(3,4);
		
		Interval e=new Interval(3,4);*/
		Interval f=new Interval(4, 5);
		List<Interval> intervals=new ArrayList<Interval>();
		intervals.add(a);
		/*intervals.add(b);
		intervals.add(c);
		intervals.add(d);
		intervals.add(e);*/
		//intervals.add(f);
		test.insert(intervals, new Interval(0, 0));
		

	}
	 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
		 this.res=intervals;
		 boolean insertFlag=false;
		 if(this.res.size()==0) {
			 res.add(newInterval);
			 return this.res;
			 }
		 List<Interval> deleteList=new ArrayList<Interval>();
		 boolean flag=false;//哨兵 判断是否发生过合并
		 for(int i=0;i<intervals.size();++i) {
			 Interval now=intervals.get(i);
			 if(judge(newInterval, now)) {
				 newInterval=merge(newInterval, now);
				 flag=true;
				 deleteList.add(now);
			 }
			 else {
				 if(flag) {//曾发生合并并且还有元素存在无法继续合并
					 this.res.get(i-1).start=newInterval.start;
					 this.res.get(i-1).end=newInterval.end;
					 deleteList.remove(deleteList.size()-1);
					 insertFlag=true;
					 break;
				 }
				 else {//无法进行合并 要么是在其左边 要么是在其右边
					 if(newInterval.end<now.start) {//在左边
						 this.insert(i,newInterval);
						 return this.res;
					 }
				 }
			 }
		 }
		 this.res.removeAll(deleteList);
		 if(!insertFlag) {
			 this.res.add(newInterval);
		 } 
	     return this.res;
	 }
	
	
	public void insert(int i, Interval newInterval) {
		this.res.add(new Interval());
		for(int j=this.res.size()-1;j>i;--j) {
			res.get(j).start=res.get(j-1).start;
			res.get(j).end=res.get(j-1).end;
		}
		this.res.get(i).start=newInterval.start;
		this.res.get(i).end=newInterval.end;		
	}
	
	public boolean judge(Interval a,Interval b) {
		if(a.end<b.start)
			return false;
		if(b.end<a.start)
			return false;
		return true;
	}
	
	public Interval merge(Interval a,Interval b) {
		return new Interval(Math.min(a.start, b.start), Math.max(a.end,b.end));
	}

}
